import unittest
import random
import time
import matplotlib.pyplot as plt
import numpy as np
from reverse_pairs import Solution

class TestReversePairs(unittest.TestCase):
    def setUp(self):
        self.solution = Solution()

    def test_empty_array(self):
        # 测试空数组
        self.assertEqual(self.solution.reversePairs([]), 0)
        print("测试空数组成功")

    def test_single_element(self):
        # 测试单个元素
        self.assertEqual(self.solution.reversePairs([5]), 0)
        print("测试单个元素成功")

    def test_reverse_order(self):
        # 测试全部逆序
        self.assertEqual(self.solution.reversePairs([5, 4, 3, 2, 1]), 4)
        # 解释：(5,2), (5,1), (4,1), (3,1) 是重要逆序对
        print("测试全部逆序成功")

    def test_increasing_order(self):
        # 测试完全递增
        self.assertEqual(self.solution.reversePairs([1, 2, 3, 4, 5]), 0)
        print("测试完全递增成功")

    def test_negative_numbers(self):
        # 测试包含负数
        self.assertEqual(self.solution.reversePairs([-5, -3, -1, 0, 2]), 1)
        self.assertEqual(self.solution.reversePairs([2, 0, -1, -3, -5]), 10)
        print("测试包含负数成功")

    def test_duplicate_elements(self):
        # 测试重复元素
        self.assertEqual(self.solution.reversePairs([2, 2, 2, 2, 2]), 0)
        self.assertEqual(self.solution.reversePairs([4, 2, 2, 2, 1]), 1)
        print("测试重复元素成功")

    def test_large_array(self):
        lengths = [1000, 2000, 4000, 8000, 16000]
        times = []

        print("\n性能测试开始：")
        print("数组长度\t运行时间(秒)")
        print("-" * 30)

        for length in lengths:
            test_array = [random.randint(-1000, 1000) for _ in range(length)]
            start_time = time.time()
            self.solution.reversePairs(test_array)
            end_time = time.time()
            run_time = end_time - start_time
            times.append(run_time)
            print(f"{length}\t\t{run_time:.8f}")

        # 绘图：比较实际时间与理论时间复杂度
        n = np.array(lengths)
        n_log_n = n * np.log2(n)
        n2 = n ** 2

        # 归一化理论时间使其和实际时间最后一个点对齐
        def normalize(ref, base):
            return [x / ref[-1] * base[-1] for x in ref]

        plt.figure(figsize=(10, 6))
        plt.plot(lengths, times, 'o-', label='Measured Time', linewidth=2)
        plt.plot(lengths, normalize(n, times), 'b--', label='O(n)')
        plt.plot(lengths, normalize(n_log_n, times), 'r--', label='O(n log n)')
        plt.plot(lengths, normalize(n2, times), 'g--', label='O(n²)')

        plt.xlabel('Input Size (n)')
        plt.ylabel('Running Time (s)')
        plt.title('Reverse Pairs Runtime vs Theoretical Complexity')
        plt.legend()
        plt.grid(True)
        plt.tight_layout()
        plt.show()
        


if __name__ == '__main__':
    unittest.main() 